#include "server/edit_distance.h"

// 计算一个字符占据的字节数
size_t nBytesCode(const char ch)
{
    // 判断是否为非 ASCII 字符
    if (ch & (1 << 7))
    {
        int nBytes = 1; // 初始假设字符占据1字节
        // 计算字符的字节数（最多6个字节，适用于UTF-8）
        for (int idx = 0; idx != 6; ++idx)
        {
            // 判断字符的高位是否为1
            if (ch & (1 << (6 - idx)))
            {
                ++nBytes; // 若高位为1，则字节数加1
            }
            else
                break; // 若高位为0，退出循环
        }
        return nBytes; // 返回计算出的字节数
    }
    return 1; // ASCII 字符占用1字节
}

// 计算字符串的实际字符长度（考虑多字节字符）
std::size_t length(const std::string &str)
{
    std::size_t ilen = 0; // 初始化字符计数
    for (std::size_t idx = 0; idx < str.size(); ++idx)
    {
        // 计算当前字符的字节数
        int nBytes = nBytesCode(str[idx]);
        // 跳过当前字符的所有字节，准备处理下一个字符
        idx += (nBytes - 1);
        ++ilen; // 有效字符计数加1
    }
    return ilen; // 返回字符总数
}

// 返回三个整数中的最小值
int triple_min(const int &a, const int &b, const int &c)
{
    return std::min(a, std::min(b, c)); // 使用std::min简化比较
}

// 计算两个字符串之间的最小编辑距离
int editDistance(const std::string &lhs, const std::string &rhs)
{
    // 获取两个字符串的字符长度
    size_t lhs_len = length(lhs);
    size_t rhs_len = length(rhs);

    // 创建二维向量来存储编辑距离动态规划的结果
    vector<vector<int>> editDist(lhs_len + 1, vector<int>(rhs_len + 1));

    // 初始化第一列：将lhs的前i个字符变为空串的代价
    for (size_t idx = 0; idx <= lhs_len; ++idx)
    {
        editDist[idx][0] = idx;
    }

    // 初始化第一行：将空串变成rhs的前j个字符的代价
    for (size_t idx = 0; idx <= rhs_len; ++idx)
    {
        editDist[0][idx] = idx;
    }

    std::string sublhs, subrhs; // 用于存储当前比较的子字符串
    // 动态规划计算编辑距离
    for (std::size_t dist_i = 1, lhs_idx = 0; dist_i <= lhs_len; ++dist_i, ++lhs_idx)
    {
        // 获取lhs的当前字符
        size_t nBytes = nBytesCode(lhs[lhs_idx]);
        sublhs = lhs.substr(lhs_idx, nBytes); // 提取当前字符的子串
        lhs_idx += (nBytes - 1);              // 更新索引，准备下一个字符

        // 内层循环，计算rhs的编辑距离
        for (std::size_t dist_j = 1, rhs_idx = 0; dist_j <= rhs_len; ++dist_j)
        {
            // 获取rhs的当前字符
            nBytes = nBytesCode(rhs[rhs_idx]);
            subrhs = rhs.substr(rhs_idx, nBytes); // 提取当前字符的子串
            rhs_idx += (nBytes - 1);              // 更新索引，准备下一个字符

            // 如果当前字符相同，则不增加编辑距离
            if (sublhs == subrhs)
            {
                editDist[dist_i][dist_j] = editDist[dist_i - 1][dist_j - 1];
            }
            else
            {
                // 计算插入、删除和替换操作的最小代价
                editDist[dist_i][dist_j] = triple_min(
                    editDist[dist_i][dist_j - 1] + 1,    // 插入
                    editDist[dist_i - 1][dist_j] + 1,    // 删除
                    editDist[dist_i - 1][dist_j - 1] + 1 // 替换
                );
            }
        }
    }
    return editDist[lhs_len][rhs_len]; // 返回最终的编辑距离
}
